package real.bytedance.tree;

import tree.TreeNode;


public class IsBalanceTree {
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        return recur(root) > 0;
    }

    public int recur (TreeNode root) {
        if (root == null) return 0;

        int left = recur (root.left);
        if (left < 0) return -1;

        int right = recur(root.right);
        if (right < 0) return -1;

        int sub = left - right;
        if (sub > 1 || sub < -1) return -1; //return -1表示不是平衡二叉樹，就不必遍歷了

        return Math.max(left, right) + 1;//若子樹符合平衡二叉樹，返回子樹的高度
    }
}
